#include <iostream>
#include <stdlib.h>

using namespace std;

// iterative binary search
const int iterBinarySearch( const int array[], 
                        const int target,
                        const int len
                      )
{
    int L = 0;                // lower bound
    int U = len-1;            // upper bound
    int range = U - L;        // search range
    int C = range/2 + 1;      // center

    try{
        while(1){
            if( L>U || range<0 ) throw "out of range !";
            
            if(range==0) // only one left
                if( array[L] == target )
                    return L;
                else
                    throw "this array does not include the number !";
            
            if( array[L]>array[U] || array[L]>array[C] ) // check sorting status
                throw "this array has not been sorted with ascending order";
            
            if( array[L] == target ) return L;
            if( array[C] == target ) return C;
            
            if( target < array[C] ){
                U = C - 1;
            }else{
                L = C + 1;
            }
            range = U - L;
            C = range/2;        
        }        
    
    }catch(char *err){
        cout << "ERROR: " << err << endl;
    }
}                        

// recursive function for search
const int binarySearch( const int array[], 
                        const int target, 
                        const int lower, 
                        const int upper )
{
    try{
        int range = upper - lower;
        
        // check index range 
        if( range < 0 || range > upper ) throw "out of range!";
        
        if( range==0 )
            if( array[lower] == target )
                return lower;
            else
                throw "target int is not in this array";
                
        int center = (int) (range/2) + lower;
        
        cout << ">> " << lower << " , " << center << " , " << upper << endl;
        
        if( array[lower] > array[center] || array[lower] > array[upper] ) 
            throw "input array order error!";
 
         // test lower one
         if( array[lower] == target ) return lower;
         
         // test central one
         if( array[center] == target ) return center;
         
         if( target < array[center] ){ // going to left side
             return binarySearch( array, target, lower, center-1 );
         }else{ // going to right side
             return binarySearch( array, target, center+1, upper );
         }                          
    }catch( char *err ){
        cout << "ERROR: " << err << endl;
    }
}

// search sorted array with ascending order
const int binarySearch( const int array[], const int target, const int len )
{
    return binarySearch( array, target, 0, len-1 );
}


int main()
{
    int array[]={ 0,3,1,2,3,4,5,4,6,7,8,9,10};
    int len = sizeof(array)/sizeof(int);
    int target = 3;
    cout << target << " at: " << iterBinarySearch( array, target, len ) << endl;    
    cout << target << " at: " << binarySearch( array, target, len ) << endl;
    
}